Order Theory - 序理论介绍

前言

我原本打算翻译一篇跟CRDT相关的文章，但是奈何找到博客都讲得过于精简，而关于CRDT的论文有把我看得一头雾水。那只能先从基础的理论开始了，以后看能不能把这些资料汇总一下。

知识点

介绍

在开始之前我们需要预热一下。首先，我们会回顾一些序理论（它是一个解决二进制关系的数学分支）的结论。徐理论中提供的一些结论是我们感兴趣的，因为有许多已发表的理论现在看来都包含了偏好关系某些形式或者其他，而且偏好关系只是二进制关系中一个特殊类型。

基础

序理论的最小分析单元是二进制关系。一个非空集合$X$的二进制关系$R$是$X\times X$的子集。换个说法就是一些有顺序的元素对组成的列表。如果${x,y}\in R$，那么$x$就和$y$有关系，相反如果${x,y}\notin R$，你妈$x$和$y$就没有关系。简便一些，如果${x,y}\in R$我们就写作$xRy$。（你应该注意到了，我们通常使用的是$\succeq$来表示二进制关系）

定义 1： 我们可以将任意二进制关系区分为对于元素对称和不对称的。我们定义前者如下

$xUy\ \ iff\ \ xRy\ \ and\ \ yRx$

以及后者如下

$xPy\ \ iff\ \ xRy\ \ but\ \ not\ \ yRx$

（ps：iff表示当且仅当）记住$R=P\cup U$。（还有我们可以单独使用$\sim$和$\succ$表示$\succeq$的对称和不对称部分）

这里有一些二进制关系可能有的属性。

定义 2： 以下是二进制关系可能有的属性：

Reflexivity（自反性）：$xRx \forall x\in X$
Symmetry（对称性）：$xRy implies yRx$
Antisymmetric（反对称性）：$if xRy then not yRx$
Asymmetric（非对称性）：$xRyRx implies that x=y$
Transitive（传递性）：$xRyRz implies xRy$
Complete（完全性）：$xRy or yRx$
Acyclic（无环性）：$x_1Rx_2R…Rx_n implies that x_1\neq x_n$

我们可以用这些属性来定义偏好关系类。

定义 3： 下面是一些偏好关系类：

如果$R$具有自反性、对称性和传递性，那么它是一个等价关系（equivalence relation）
如果$R$具有自反性和传递性，那么它是一个预序关系（preorder）
如果$R$具有自反性、传递性和反对称性，那么它是一个偏序关系（partial order）
如果一个偏序关系具有完全性，那么它是一个线序关系（linear order）

注意预序和偏序有差异。前者不允许反对称性，而后者允许。

我们称一个集合和一个陪伴的二进制关系$(X,R)$为偏序集合（poset）仅当$R$是一个偏序关系，为线序集合（loset）仅当$R$是一个线序关系。

一个等价关系允许我们定义等价类的概念。一个元素$x$的等价类包含了所有$x$有关的元素。这样如果$\sim$是集合$X$的一个等价关系，我们定义$x\in X$的等价类如下

$[x]_{\sim}=\{y\in X\mid x\sim y\}$

我们也可以定义$X$关于$\sim$的商集（quotient set）。这是一个等价类集合的集合。

定义 4： 对于集合使用等价关系$\sim$会生成一个商集，定义如下

$X\backslash_{\sim}=\{[x]_{\sim}\ x\in X\}$

对于任意二进制关系，我们可以定义最大元素和上界（upper bound）的概念：

定义 5：已知$\succeq$是集合$X$的一个二进制关系：集合$X$根据$\succeq$的最大元素的定义是

$Max(X,\succeq)=\{x\in X\mid y\succ x\ \ for\ no\ y\in X\}$

而上界的定义是

$M(X,\succeq)=\{x\in X\mid x\succeq y\ \ \forall\ \ y\in X\}$

你可能会直观地把上界和最大元素想成是等价的，但是普遍情况下对于任意二进制关系，这不是一回事。

传递闭包和传递扩展

有个我们感性兴趣的问题是，我们观察到的二进制关系，是否能被看作是某些完全预序的不完全视角（我把glimpse翻译为了“视角”，也不知道对不对，暂时先这样）。为了回答这个问题，我们需要介绍传递闭包和扩展的概念。

定义 6： 一个二进制关系$R$的传递闭包也是一个二进制关系$T(R)$，而且是包含$R$的最小传递关系。（举例：$T(R)$是传递的，就意义上而言它包含了$R$，$xRy$蕴含了$xT(R)y$，并且任意更小（从子集层面上）的二进制关系都是不传递或者不包含$R$）

传递闭包对于我们的将要了解的东西很有帮助，所以值得描述一下他们的属性。

备注 1： 任意集合$X$的每个二进制关系$R$都有一个传递闭包。

证明 . 这里我们注意到总是存在一个包含$R$的传递二进制关系：$xTy$中$x,y\in X$。此外，任意传递关系集合的交集本身就是传递的。这样所有包含$R$的传递关系的交集总是存在的，而且是包含了$R$的最小传递闭包关系。$\blacksquare$

备注 2： 我们可以交替定义二进制关系$R$的传递闭包如下：

定义$R_0=R$
如果存在$z_1,z_2,…,z_m\in X$使得$xRz_1R…Rz_mRy$，定义$R_m$简化表达式为$xR_my$
$T=R\cup_{i\in\mathbb{N}}R_i$

证明 . 我们需要谈三个点 — $R$包含于$T$，$T$是传递的，任意包含$R$的传递集合也包含了$T$。第一点很好理解。第二点来看实际情况，如果$xTyTz$，那么$xR_myR_nz$，其中$m,n\in\mathbb{N}$。这样存在$xR_pz$，其中$p\leq m+n$，所以就有$xTz$。最后已知$G$是一个包含$R$的传递集合。我们需要证明这个集合也包含了$T$。同样的我们也需要证明对于每个$i$它都包含了$R_i$。我们可以归纳证明这一点。很明显$G$包含了$R_0$，也就是$R$。现在假设它包含了$R_n$，这是某个$x$和$y$的关系，对于某些关系

$xR_{z_1}R...R_{z_n}R_{z_{n+1}}Ry$

的$z_1,…z_{n+1}$。根据归纳假设，我们已知$xGz_{n+1}$和$z_{n+1}Gy$。这样根据$G$的传递性得出$xGy$，所以由此可见$G$包含了$T$，证毕。$\blacksquare$

定义 7： 已知$\succeq$是集合$X$的一个预序关系。一个$\succeq$的传递扩展也是一个预序关系使得

$\succeq\ \subset\ \unrhd$ $\succ\ \subset\ \rhd$

换句话说，一个预序关系$\succeq$的扩展是另外一个预序关系，从某种程度上它“认同”关系$\succeq$，也就是$x\succeq y$包含于$x\unrhd y$，但是$x\succ y$意味着一定不会存在$y\unrhd x$。

我们特别感兴趣的是预序$\succeq$的完全传递扩展，也就是$succeq$的传递扩展，而且具有完整性。序理论的一个基本结论是，每个偏序都能扩展成一个线序。对于任意集合$X$的一个预序，不管它的基数如何，这个结论也成立。

定理 1（Sziplrajn）： 对于任意非空集合$X$和偏序关系$\succ$，一定存在一个线序（拓扑排序），而且它是$\succ$的一个传递扩展。

此处我有一个疑问，这个定理为真就意味着，集合X中任意两个元素都直接或者间接存在关系。比如集合X={A,B,C,D,E}中的元素表示城市，定义一个偏序关系≥是“两个城市之间存在直达的道路”，(A,B)表示城市A和B之间存在直达的道路。假设存在关系(A,B)、(B,C)、(D,E)，现在将≥传递扩展成≥1 — “通过最多两条路可以到达的城市”，得到新的元素关系(A,B)1、(B,C)1、(A,C)1、(D,E)1。但是不管我们将通过的道路数量扩展为多少条，{A,B,C}和{D,E}中的元素就是完全没有关系（直接或者间接）。所以不管怎么做传递扩展都不能得到一个关系≥n使得(X,≥n)具有完全性。

这里应该是我对“传递扩展”或者“偏序集”存在什么误解，希望以后能解开我这里的疑惑。

这里$X$是有限的，Sziplrajn的定理很容易证明。然而如果$X$是任意集合，那就需要在一些公理的形式下进行更多数学运算。稍后我们会讨论证明，但是在此之前，值得注意一下这个定义本身的含义，明确一点同样的结论用在预序上也没问题。

协理 1： 对于任意非空集合$X$和预序$\succeq^{*}$，一定存在一个完全预序，并且它是$\succeq^{*}$的一个传递扩展。

证明 . 已知$\sim$是$\succeq^{*}$的对称部分。$\sim$是一个等价关系。我们可以使用$\succeq^{*}$来生成一个商集$X\backslash_{\sim}$偏好关系$\unrhd^{*}$，方式如下：

$[x]_{\sim}\ \unrhd^{*}\ [y]_{\sim}\ if\ and\ only\ if\ x\succeq^{*} y$

很明显$\unrhd^{*}$是一个商集$X\backslash_{\sim}$的一个偏序关系。这样，根据Sziplrajn的理论，一定存在一个基于$X\backslash_{\sim}$的线性关系$\unrhd$，它是$\unrhd^{*}$的传递扩展。定义$X$的偏好关系$\succeq$如下

$x\succeq y\ if\ and\ only\ if\ [x]_{\sim}\unrhd [y]_{\sim}$

仔细思考一下你会发现$\succeq$就是由$\succeq^{*}$传递扩展得到的一个完全预序。

另外一个对于这个结论的灵活概括是不仅仅只有预序可以传递扩展成完全预序。事实上，一个充分（以及必要）条件是一个非循环性质的变体，我称之为弱循环性质（OWC - only weak cycle）

定义 8： 已知$\succeq$s是一个非空集合$X$的关系，$\succ$是$\succeq$和$T(\succeq)$的非对称部分。我们说$\succeq$满足弱循环性质仅当

$xT(\succeq)y\ implies\ not\ y\succ x$

正如其名，OWC条件是一个比非循环性质更弱的条件 — 它允许环的存在，但是仅限于$\succeq$的对称部分。还要注意，这个条件与显示性偏好的广义公理（Generlized Axiom of Revealed Preference）密切相关。

命题 1： 已知$\succeq$是任意一个非空集合$X$的二进制关系。那么$\succeq$能被传递扩展成一个完全预序当且仅当它满足OWC

证明（OWC意味着完全预序传递扩展的存在） . 已知$T(\succeq)$是$\succeq$的传递闭包，而且在$X$上有自反关系。如果$\succeq$满足$OWC$，那么$T(\succeq)$就是一个$\succeq$的传递扩展。这个结论来自于OWC条件，因为如果$y\succ x$，不可能存在关系$T(\succeq)y$。此外$T(\succeq)$是一个预序，因为它具有传递性的自反性。这样根据协理1，一定存在一个$T(\succeq)$的传递扩展是完全预序，那么$\succeq$也不例外，证毕。$\blacksquare$

证明（完全预序传递扩展的存在意味着OWC）. 假设$\succeq$违反了OWC，那么一定存在一个$x$和$y$使得

$xT(\succeq)y\ and\ y\succ x$

在任何$\succeq$的传递扩展$R$中，不可能存在$xRy$但$R$不具备传递性。

选择公理（The Axiom of Choice）

为了证明Sziplrajn的定理，我们将会用到选择公理。我们只是简单使用一些高级的吉和理论，并不会具体讲清楚。但是因为这些结论在决策理论中被反复提及，值得我们在这里快速的概括一下他们。

选择公理让人觉得困惑，但是它的概念是这样的：已知$\mathcal{A}$是一个任意非空集合的集合。我们想知道的是：在什么情况下我们可以构造一个函数，他能从每个元素集合中选出一个元素。换句话说，在什么情况下我们能构造一个函数

$\begin{align}f:\mathcal{A}\rightarrow\cup\mathcal{A} \\ such\ that\ f(a)\in A\forall A\in\mathcal{A}\end{align}$

换个说法，如果我们面前有一堆箱子，在什么情况下我们能确保我们能找到一种方式从每个箱子中选中一个物品。

从字面上看，我们总是能做到这个要求。在很多情况下，很容易证明这是事实。比如：

如果$\mathcal{A}$由一些自然数集合组成，那么我们能构造这样一个函数：我们定义一个函数来获取每个集合中的最小数字。
如果$\mathcal{A}$是实线上的间距，那么我们能构造这样一个函数：我们定义一个函数来获取线段的中点。
如果$\mathcal{A}$是无限的，那也许我们不能构造这样一个函数（如果我们不知道集合中是什么东西），但是我们知道一个现有的。让我们枚举这些集合$A_1,…A_n$。事实上$A_1\in\mathcal{A}$是非空意味着存在某个元素$a_1\in A_1$。这样我们让$f(A_1)=a_1$。根据归纳法我们可以将这个原理扩展到任意包含$n$个集合的集合。

问题来了如果我们的集合$\mathcal{A}$同时包含了一个有限的数字集合和其他我们不知道性质的集合。所以如果$\mathcal{A}$是实线的所有子集。这里我们不能构造一条明确的规则（你可以尝试，但是你找不到一条适用于实线的任意子集的规则），而且我们不能使用归纳法来证明存在这样一条规则，所以我们怎么知道这些规则的存在呢？

答案是否定的：这表明标准数学公理（(the ZermeloFraenkel-Skolem axioms）不能保证任意非空集合的集合有一条这样的规则存在。然而，同样的情况是，这种规则的存在与其他公理一致。因此，这种规则的存在独立于数学的其他部分：我们可以有一个一致的数学系统，在其中假定这个规则总是存在，或者假设它不存在。换句话说，我们可以选择是否接受选择公理。

定义 9（选择公理）： 已知$\mathcal{A}$是一个任意的非空集合的集合。那么一定存在一个函数

$\begin{align}f:\mathcal{A}\rightarrow\cup\mathcal{A} \\ such\ that\ f(a)\in A\forall A\in\mathcal{A}\end{align}$

现如今的大多数学家选择相信选择功能，部分原因是它看起来如此直观。虽然你需要小心 — 选择公理可能会有一些非预期的后果。其中一个（the Banach-Tarski paradox）是，如果我们接受选择公理，那么一个三维空间中的固体球能被分解成有限数量的不重叠碎片，他们又能通过不能的方式组合生成两个原始球的两个相同副本。重组的过程包括移动和旋转碎片，不改变其形状。

忽略这个有点糟糕的结论，接下来我们将会试用选择公理。因为它非常好用。比如下面例子都是真的当且仅当选择公理成立：

任意数量的非空集合的笛卡尔积都是定义明确的。
(Zornís Lemma)如果一个已知偏序集的每个线序集都有一个上界，那么这个线序最多只有一个极大元。
(The Hausdor§ Maximum principle) 每个偏序集存在一个$\supseteq$-最大的线序集。（存在一个线序集$\{X,\succeq\}$使得没有其他的线序集$\{Y,\succeq\}$可以让$Y\supset X$）

我们可以用这些来证明Sziplrajn的定理（切记，事实上这个定理并不等价于选择公理）

(Sziplrajn的定理). 已知$\succeq$是一个非空集合的偏序。让$T_X$作为所有$\succeq$传递扩展的偏序关系集合。很明显$\{T_X,\supseteq\}$是一个偏序集合，所以根据the Hausforff maximum principle，一定有一个最大的线序集$\{A,\supseteq\}$。定义$\succeq^{*}=\cup A$（所有$A$中二进制关系的并集）。因为$A$是一个线序集（所以所有$A$中的元素都能用子集关系来排序），那么$\succeq^{*}$是一个$\succeq$传递扩展得到的偏序。此外，$\succeq^{*}$具有完全性。为了证明这一点，我们假设不是这样，那么选取某个$x,y$使得既非$x\succeq^{*}$也非$y\succeq^{*}$。那么，如果我们求$\succeq^{*}\cup\{x,y\}$的传递闭包，可以得到一个$T_X$的元素，它包含$\succeq^{*}$作为子集。但这与事实$\{A,\supseteq\}$是$\{T_X,\supseteq\}$中的最大线序集相矛盾。$\blacksquare$

原文链接

http://www.columbia.edu/~md3405/DT_Order_15.pdf